package gameoflife.automaton;

import gameoflife.Cell;
import gameoflife.Heading;
import gameoflife.Pattern;
import gameoflife.Position;
import gameoflife.Rule;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class BitBlockAutomaton extends AbstractAutomaton {

	private Map<Position, BitBlock> map = new HashMap<Position, BitBlock>();
	private ArrayList<Position> disposables = new ArrayList<Position>();
	private ArrayList<Position> newNonEmpty = new ArrayList<Position>();

	private int births = 0;
	private int deaths = 0;
	private int size = 0;

	private final ReadWriteLock lock = new ReentrantReadWriteLock();
	private final Lock mapRead = lock.readLock();
	private final Lock mapWrite = lock.writeLock();

	public BitBlockAutomaton() {
		BitBlock.setTransformRule(rule);
	}

	@Override
	protected void step() {
		int stepBirths = 0;
		int stepDeaths = 0;

		// compute
		disposables.clear();
		newNonEmpty.clear();
		for (Map.Entry<Position, BitBlock> e : map.entrySet()) {
			BitBlock block = e.getValue();

			if (block.isDisposable()) {
				disposables.add(e.getKey());
			}
			else {
				block.computeNext();
				stepBirths += block.births;
				stepDeaths += block.deaths;
 				if (block.matrix == 0 && block.next != 0) {
					newNonEmpty.add(e.getKey());
				}
			}
		}

		// book-keeping and flip
		mapWrite.lock();
		{
			generation++;
			births = stepBirths;
			deaths = stepDeaths;
			size += (births - deaths);

			// remove disposable blocks
			for (Position p : disposables) {
				map.remove(p).dispose();
			}

			for (BitBlock block : map.values()) {
 				block.flip();
			}

			// always keep empty blocks around non-empty ones
			final Position neighbor = new Position();
			for (Position position : newNonEmpty) {
				for (Heading heading : Heading.ALL) {
					heading.toPosition(position, neighbor);
					if (!map.containsKey(neighbor)) {
						map.put(new Position(neighbor), new BitBlock(map, neighbor));
					}
				}
			}
		}
		mapWrite.unlock();
	}

	@Override
	public void accept(Visitor visitor) {
		mapRead.lock();
		try {
			final Cell cell = new Cell();
			for (Map.Entry<Position, BitBlock> e : map.entrySet()) {
				int matrix = e.getValue().matrix;
				if (matrix != 0) {
					Position position = e.getKey();
					int x = position.getX() << 2;
					int y = position.getY() << 2;
					int n = 0;
					do {
						if ((matrix & 1) != 0) {
							cell.moveTo(x + (n & 3), y + (n >> 2));
							visitor.visit(cell);
						}
					    n++;
					} while ((matrix >>>= 1) != 0);
				}
			}
		} finally {
			mapRead.unlock();
		}
	}

	@Override
	public synchronized void setRule(Rule rule) {
		super.setRule(rule);
		BitBlock.setTransformRule(rule);
	}

	private Position toMapPosition(Position p) {
		return new Position(p.getX() >> 2, p.getY() >> 2);
	}

	private int toBlockIndex(Position p) {
		return ((p.getY() & 3) << 2) + (p.getX() & 3);
	}

	private void add(Position position) {
		Position mapPosition = toMapPosition(position);
		BitBlock block = map.get(mapPosition);
		if (block == null) {
			block = new BitBlock(map, mapPosition);
			map.put(mapPosition, block);
		}
		int original = block.matrix;
		block.matrix |= (1 << toBlockIndex(position));
		if (original != block.matrix) {
			size++;
			// always keep empty blocks around non-empty ones
			for (Heading heading : Heading.ALL) {
				Position neighborPosition = heading.toPosition(mapPosition);
				if (!map.containsKey(neighborPosition)) {
					map.put(neighborPosition, new BitBlock(map, neighborPosition));
				}
			}
		}
	}

	private void remove(Position position) {
		Position mapPosition = toMapPosition(position);
		BitBlock block = map.get(mapPosition);
		if (block != null) {
			int original = block.matrix;
			block.matrix &= ~(1 << toBlockIndex(position));
			if (original != block.matrix) {
				size--;
				if (block.isDisposable()) {
					map.remove(mapPosition).dispose();
				}
			}
		}
	}

	@Override
	public synchronized void set(Position position, boolean value) {
		mapWrite.lock();
		if (value) {
			add(position);
		}
		else {
			remove(position);
		}
		mapWrite.unlock();

		stateChanged(0);
	}

	@Override
	public synchronized void addAll(Collection<Position> positions) {
		mapWrite.lock();
		for (Position position : positions) {
			add(position);
		}
		mapWrite.unlock();

		stateChanged(0);
	}

	@Override
	public synchronized void clear() {
		mapWrite.lock();
		map.clear();
		births = 0;
		deaths = 0;
		generation = 0;
		size = 0;
		mapWrite.unlock();

		stateChanged(0);
	}

	@Override
	public synchronized boolean isSet(Position position) {
		BitBlock block = map.get(toMapPosition(position));
		if (block != null) {
			int n = toBlockIndex(position);
			return (block.matrix & (1 << n)) != 0;
		}
		return false;
	}

	@Override
	public synchronized Cell getCell(Position position) {
		return isSet(position) ? new Cell(position) : null;
	}

	@Override
	public synchronized int size() {
		return size;
	}

	@Override
	public synchronized int births() {
		return births;
	}

	@Override
	public synchronized int deaths() {
		return deaths;
	}

	@Override
	public synchronized Pattern toPattern() {
		final Collection<Position> positions = new ArrayList<Position>(map.values().size());
		accept(new Visitor() {
			@Override
			public void visit(Cell cell) {
				positions.add(new Cell(cell));
			}
		});
		return new Pattern(getRule(), positions);
	}

}
